翻訳と辞書
Words near each other
・ Quark Publishing System
・ Quark star
・ Quantum Theatre
・ Quantum Theology
・ Quantum theory
・ Quantum Theory (video game)
・ Quantum thermodynamics
・ Quantum threshold theorem
・ Quantum tic-tac-toe
・ Quantum tomography
・ Quantum topology
・ Quantum triviality
・ Quantum tunnelling
・ Quantum tunnelling composite
・ Quantum turbulence
Quantum Turing machine
・ Quantum vacuum thruster
・ Quantum valebant
・ Quantum vortex
・ Quantum walk
・ Quantum well
・ Quantum well infrared photodetector
・ Quantum well laser
・ Quantum wire
・ Quantum yield
・ Quantum Zeno effect
・ Quantum-class cruise ship
・ Quantum-confined Stark effect
・ Quantum-mechanical explanation of intermolecular interactions
・ Quantum-optical spectroscopy


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Quantum Turing machine : ウィキペディア英語版
Quantum Turing machine

A quantum Turing machine (QTM), also a universal quantum computer, is an abstract machine used to model the effect of a quantum computer. It provides a very simple model which captures all of the power of quantum computation. Any quantum algorithm can be expressed formally as a particular quantum Turing machine. Such Turing machines were first proposed in a 1985 paper written by Oxford University physicist David Deutsch suggesting quantum gates could function in a similar fashion to traditional digital computing binary logic gates.〔

Quantum Turing machines are not always used for analyzing quantum computation; the quantum circuit is a more common model. These models are computationally equivalent.
Quantum Turing machines can be related to classical and probabilistic Turing machines in a framework based on transition matrices, shown by Lance Fortnow.
Iriyama, Ohya, and Volovich have developed a model of a Linear Quantum Turing Machine (LQTM). This is a generalization of a classical QTM that has mixed states and that allows irreversible transition functions. These allow the representation of quantum measurements without classical outcomes.〔 also 〕
A quantum Turing machine with postselection was defined by Scott Aaronson, who showed that the class of polynomial time on such a machine (PostBQP) is equal to the classical complexity class PP.〔 Preprint available at ()〕
== Informal sketch==
An easy way of understanding the quantum Turing machine (QTM) is that it generalizes the classical Turing machine (TM) in the same way that the quantum finite automaton (QFA) generalizes the deterministic finite automaton (DFA). In essence, the internal states of a classical TM are replaced by pure or mixed states in a Hilbert space; the transition function is replaced by a collection of unitary matrices that map the Hilbert space to itself.
That is, a classical Turing machine is described by a 7-tuple M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle. For a three-tape quantum Turing machine (one tape holding the input, a second tape holding intermediate calculation results, and a third tape holding output),
* The set of states Q is replaced by a Hilbert space.
* The tape alphabet symbols \Gamma are likewise replaced by a Hilbert space (usually a different Hilbert space than the set of states).
* The blank symbol b \in \Gamma corresponds to the zero-vector.
* The input and output symbols \Sigma are usually taken as a discrete set, as in the classical system; thus, neither the input nor output to a quantum machine need be a quantum system itself.
* The transition function \delta : \Sigma \times Q \otimes \Gamma \rightarrow \Sigma \times Q \otimes \Gamma \times \ is a generalization of a transition monoid, and is understood to be a collection of unitary matricies that are automorphisms of the Hilbert space Q.
* The initial state q_0 \in Q may be either a mixed state or a pure state.
* The set F of ''final'' or ''accepting states'' is a subspace of the Hilbert space Q.
The above is merely a sketch of a quantum Turing machine, rather than its formal definition, as it leaves vague several important details: for example, how often a measurement is performed; see for example, the difference between a measure-once and a measure-many QFA. This question of measurement affects the way in which writes to the output tape are defined.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Quantum Turing machine」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.